package leetcode

import kotlinetc.println

//https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
/**
Given an sort.getArray of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the sort.getArray, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
 */
//TODO
fun main(args: Array<String>) {
    searchRange(intArrayOf(5, 7, 7, 8, 8, 10), 8).asList().println()
}

fun searchRange(nums: IntArray, target: Int): IntArray {
    if (nums.isEmpty() || target < nums[0] || target > nums.last()) return intArrayOf(-1, -1)


    var l = 0
    var r = nums.size - 1

    var mid = (l + r + 1) / 2
    while (l <= r) {
        val m = nums[mid]
        if (m == target) {
            var left = mid
            while (--left >= 0 && nums[left] == m);
            left++

            var right = mid
            while (++right < nums.size && nums[right] == m);
            right--

            return intArrayOf(left, right)
        }

        if (target > m)
            l = mid + 1
        else r = mid - 1

        mid = (l + r + 1) / 2
    }

    return intArrayOf(-1, -1)
}